package array

/*
	以[3,4,7,2,-3,1,4,2]为例
	pre分别为[3,7,14,15,13,14,18,20]
	pre[5]-pre[1]=nums[2]+num[3]+nums[4]+nums[5]=k
*/
func subarraySum(nums []int, k int) int {
	pre, count := 0, 0
	// 第一个int用来记录以nums[i]结尾的前缀和的大小
	// 第二个int用来记录该前缀和的个数
	// m用来存放前缀和为int1的个数
	m := map[int]int{}
	// 因为从nums[0]开始遍历，nums[0]之前的前缀和为0
	m[0] = 1
	for _, v := range nums {
		pre += v // 以当前元素为结尾的前缀和

		/*
			判断是否存在pre[i]-pre[j]==k
			即是否存在 nums[j+1]+...nums[i]==k
			map[pre[i]-k]就是pre[j]可能的情况个数
		*/
		if _, ok := m[pre-k]; ok {
			count += m[pre-k]
		}
		m[pre]++ // 当前前缀和的值的个数+1
	}

	return count
}
